#include "BinarySearchTree.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

template <typename Comparable>
void BST_sort(std::vector<Comparable> &_data){
    BinarySearchTree<Comparable> B;
    long int size = _data.size();
    for(int i=0;i<size;i++){
        B.insert(_data[i]);
    }
    B.printTree();
}

template <typename Comparable>
void Randomized_BST_sort(std::vector<Comparable> &_data){
    BinarySearchTree<Comparable> R;
    long int size = _data.size();
    vector<Comparable> T=_data;
    for(int i=0;i<size;i++){
        R.insert(_data[i]);
    }
    R.random_shuffle(_data);
    cout<<"The randomized vector is "<<endl;
    for(int i=0;i<size;i++){
        cout<<_data[i];
    }
    cout<<"The RandomizedBST is :"<<endl;
    BST_sort(_data);
    R.printTree();
}

int main(){
    int a,b;
    BinarySearchTree<int> Tree;
    cout<<"Enter the length of BST vector: ";
    cin>>a;
    cout<<"Enter the length of RandomizedBST vector: ";
    cin>>b;
    vector<int> v1(a),v2(b);
    
    cout<<"Enter the elements of BST vector: ";
    for(int i=0;i<a;i++){
        cin>>v1[i];
    }
    cout<<"The BST vector is: "<<endl;
    for(int i=0;i<a;i++){
        cout<<v1[i]<<" ";
    }
    
    cout<<endl<<"Enter the elements of RandimizedBST vector: ";
    for(int i=0;i<b;i++){
        cin>>v2[i];
    }
    cout<<"The RandomizedBST vector is: "<<endl;
    for(int i=0;i<b;i++){
        cout<<v2[i]<<" ";
    }
    cout<<endl<<"After sort, the BST is : "<<endl;
    BST_sort(v1);
    cout<<endl<<"After sort, the RandomizedBST is : "<<endl;
    Randomized_BST_sort(v2);

    return 0;
}
